Error correction and error detection codes have been used extensively in data communication and data storage applications. In a data communication application, data is encoded prior to transmission, and decoded at the receiver. In a data storage application, data is encoded when stored in a storage device, e.g. in a disk drive, and decoded when retrieved from the storage device.
In a typical application of error detection and correction codes, data symbols are stored in blocks, wherein each block of data symbols includes a selected number of special symbols, called check symbols. A symbol may consist of a single bit or multiple bits. The check symbols in each block represent redundant information concerning the data stored in the block. When decoding the blocks of data, the check symbols are used to detect both the presence and the locations of errors and, in some instances, to correct these errors. The theory and applications of error correction codes are well-known to those skilled in the art. For reference, please see “Error Control Coding: Fundamentals and Applications”, by Shu Lin and Daniel J. Costello, Jr., Prentice-Hall, 1983.
In a typical application of error correction codes, the input data is divided into fixed-length blocks (“code words”). For a linear block (n, k) code, each code word consists of n symbols, of which fixed number k is data symbols, and the remaining (n-k) symbols are check symbols. The linear block code can be defined in terms of generator and parity-check matrices. As mentioned above, the check symbols represent redundant information about the code word and can be used to provide error correction and detection capabilities.
The decoding of linear block codes typically is based on a set of “syndromes” computed from a remainder polynomial. The set of “syndromes” is obtained by dividing the code word by the generator polynomial. Ideally, if no error is encountered during the decoding process, all computed syndromes are zero. A non-zero syndrome indicates that one or more errors exist in the code word. Depending on the nature of the generator polynomial, the encountered error may or may not be correctable. If the generator polynomial can be factorized, a syndrome computed from the remainder polynomial obtained by dividing the received code word by one of the factors of the generator polynomial is called a “partial syndrome”.
One can view the code words as occupying the vertices of a cube in an n-dimensional space. Choosing a good set of code words for a code consists of choosing a set of vertices which have good distance properties in the n-dimensional space. The probability of error between two blocks of binary digits is reduced by increasing the Hamming distance between the code words, which is defined as the number of symbol positions at which two code words differ. In such an error correction code, two code words differ by a distance of one, if they differ at one symbol position, regardless of the number of bit positions these code words differ within the corresponding symbols at that symbol position.
The capability of an error correction or detection code is sometimes characterized by the size of the maximum error burst the code can correct or detect. For example, a convenient capability measure is the “single error burst correction” capability, which characterizes the code by the maximum length of consecutive error bits the code can correct, as measured from the first error bit to the last error bit, if a single burst of error occurs within a code word. Another example of a capability measure would be the “double error burst detection” capability, which characterizes the error correction or error detection code by the maximum length of each error burst the error correction code can detect, given that two or less bursts of error occur within a code word.
Because errors often occur in bursts in some types of channels (for instance, in the Rayleigh fading channel), a technique, called “interleaving”, is often used to spread the consecutive error bits or symbols into different “interleaves”, which can each be corrected individually. Interleaving is achieved by creating a code word of length ‘nw’ from ‘w’ code words of length ‘n’. In one method for forming the new code word, the first w symbols of the new code word are provided by the first symbols of the w code words taken in a predetermined order. In the same predetermined order, the next symbol in each of the w code words is selected to be the next symbol in the new code word. This process is repeated until the last symbol of each of the w code words is selected in the predetermined order into the new code word.
Another method to represent a w-way interleaved code is to replace a generator polynomial G(X) of an (n, k) code by the generator polynomial G(Xw). This technique is applicable, for example to the Reed-Solomon codes. Using this new generator polynomial G(Xw), the resulting (nw, kw) code has the error correcting and detecting capability of the original (n, k) code in each of the w interleaves so formed.
There are two basic types of prior art interleaver: a block interleaver and a convolutional interleaver. The block interleaver has a rectangular configuration and is represented by a matrix having N number of columns and M number of rows, that is the block interleaver includes two interleaving parameters: (N, M). The input data is typically written into the block interleaver by column, and is read out by row. On the receiving end, after the data is transmitted over a channel generating bursts of errors, the block de-interleaver writes the received data by row, and reads the data out by column, thus randomly spreading the bursts of errors in time.
A convolutional prior art interleaver has two interleaving parameters: a number of branches L, and a delay D: (L, D). The first branch of the convolutional interleaver includes a minimum delay zero, wherein the last L-th branch includes the maximum delay: (L−1)D. A convolutional de-interleaver includes the matching parameters: the L number of branches, and the same D delay. However, the last L-th branch of the convolutional de-interleaver includes a minimum delay zero, wherein the first branch includes the maximum delay: (L−1)D. For a digital video broadcast channel (DVB channel), the parameters of the convolutional interleaver are such: there are L=12 branches, and the delay D=17.